package org.laizili.solution.leetcode;

import java.util.stream.IntStream;

/**
 * <a href="https://leetcode.cn/problems/can-i-win/">464. 我能赢吗</a>
 * <p>
 * tags: 博弈; 状态压缩+记忆化搜索+DFS
 */
public class Problem464 {
    private static class Solution {


        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            int sum = IntStream.range(1, maxChoosableInteger + 1).sum();
            if (sum < desiredTotal) {
                return false;
            }
            Boolean[] dp = new Boolean[1 << maxChoosableInteger];
            return dfs(maxChoosableInteger, desiredTotal, 0, dp);
        }

        // TODO: 博弈过程分析(搜索)
        private boolean dfs(int maxChoosableInteger, int desiredTotal, int leftNumber, Boolean[] dp) {
            if (dp[leftNumber] != null)
                return dp[leftNumber];
            for (int i = 0; i < maxChoosableInteger; i++) {
                if ((leftNumber & (1 << i)) == 0) {
                    // 本轮必赢 + 后续对方必输
                    if (desiredTotal - i - 1 <= 0 ||
                            !dfs(maxChoosableInteger, desiredTotal - i - 1, leftNumber | (1 << i), dp)) {
                        return dp[leftNumber] = true;
                    }
                }
            }
            return dp[leftNumber] = false;
        }

    }

    public static void main(String[] args) {
        System.out.println(new Solution().canIWin(3, 4));
    }
}
